Computer networking is generally recognized as the communication of packets across an interconnected network of computers. One objective of networking is to quickly forward the packets from a source to a destination. Thus, one or more forwarding devices may be placed within the network for performing such a function. As used herein, the term “forwarding devices” can be used interchangeably to refer to gateways, bridges, switches, or routers.
A forwarding device typically includes a lookup table containing a representation of at least a portion of the network topology, as well as current information about the best known paths (or “routes”) from the forwarding device to one or more destination addresses. For example, a forwarding device may store address prefixes (or “prefix entries”) and next hop identifiers in a lookup table. The prefix entries generally represent a group of destination addresses that are accessible through the forwarding device, whereas next hop identifiers represent the next device along the path to a particular destination address. Other information may be stored within the lookup table, such as the outgoing port number, paths associated with a given route, time out values and one or more statistics about each route.
When an incoming address is received by a forwarding device, the address is compared to the prefix entries stored within the lookup table. If a match occurs, the packet of information associated with the address is sent to an appropriate output port of the forwarding device. As links within the network change, routing protocols sent between forwarding devices may change the prefix entries within the corresponding lookup tables. This change will modify not only the prefix entries within the lookup table, but also the next-hop identifiers pointed to by those prefix entries. Thus, routing through the forwarding devices can be dynamically changed (i.e., updated) as links go down and come back up in various parts of the network.
The Internet Protocol (IP) is the protocol standard most widely used for packet communication to and from the Internet. Internet Protocol (IP) addresses associated with a packet generally comprise a network field (for identifying a particular network) and a host field (for identifying a particular host on that network). All hosts on the same network have the same network field but different host fields. In “class-based” addressing architectures, the IP address space is partitioned into a number of different classes (e.g., classes A-E), each distinguished by the number of bits used to represent the network field. For example, a class ‘A’ network may be represented by a 7-bit network field and a 24-bit host field, whereas a class ‘C’ network may be represented by a 21-bit network field and an 8-bit host field. The number of bits dedicated to the network and host fields may vary from class to class in the class-based addressing architecture. As network traffic increased, however, class-based architectures began to suffer from various problems; namely, the impending depletion of IP address space and the exponential growth of lookup tables.
In an attempt to slow the growth of lookup tables and allow more efficient use of the IP address space, an alternative addressing and routing scheme referred to as Classless Inter-Domain Routing (CIDR) was adopted in 1993. The “classless” addressing architecture improved upon the class-based architecture by varying the boundary between the network field and the host field. In other words, the use of classless addressing architectures enabled network fields to be made of arbitrary length, rather than constraining them to fixed network-host field boundaries. Though beneficial in alleviating the above problems, the change from class-based to classless addressing architectures only increased the complexity and reduced the speed of the lookup operation.
In addition to class-based and classless addressing architectures, there are currently several versions of IP addressing. For instance, IP version 4 (IPv4) uses a 32-bit addressing prefix, whereas IP version 6 (IPv6) uses a 128-bit addressing prefix. If, for example, IPv4 addressing is used, then the forwarding device might only consider the first 8, 16 or 24 bits of the 32-bit addressing field in determining the next hop. The number of bits considered by the forwarding device is typically referred to as the prefix length (p).
A popular way to determine the next hop is to use a technique known as longest-matching prefix. In this technique, a 32-bit IP address of, for example, 192.2.8.64 is compared against a prefix entry (or “prefix”) within the lookup table. The prefix 192.2.0.0/16 has a longer matching prefix than prefix 192.0.0.0/8. This is due primarily to the prefix length in the former being 16 bits, and the prefix length in the latter being only 8 bits. When employing the longest matching prefix technique, the forwarding device will initially consider the first two bytes of 192.2* to determine the next hop address at which to send the packet.
There are many ways to perform a longest-matching prefix comparison. For example, pointers or hashes may be used to divide the lookup table into a plurality of sub-databases, each representing a different route through the network. To locate individual sub-databases, the first few bits of a binary prefix entry may be stored as a pointer within a pointer table. Each pointer entry keeps track of the prefixes within a particular sub-database, and points to subsequent binary entries needed to complete the longest prefix match. Unfortunately, many routes (empty routes) pointed to by the pointer entry may never be used (i.e., never compared with the incoming address). Moreover, while some routes (sparse routes) might seldom be used, other routes (dense routes) are used more often. Therefore, many sub-databases may be empty or sparse of any prefix entries matching the incoming addresses. Dividing a database of prefixes using precursor pointers, while heuristic, does not assure that the databases will be optimally divided. Moreover, the above technique does not provide any worst-case guarantees on lookup performance.
Another technique used to divide a database may involve the use of a tree (or “trie”). There are many different tree configurations. A simple tree is often referred to as a binary tree, with more complex trees being compressed forms of the binary tree. To search for an address within a tree, the search begins at a root node. Extending from the root node, a “1” pointer or a “0” pointer is followed to the next node, or the next binary bit position, within the tree. If, for example, the address begins with 001*, then the search begins at the root node and proceeds downward to each vertex node, beginning along the “0” branch pointer to the next “0” branch pointer, and finally to the “1” branch pointer. The search will continue until a leaf node is reached or a failure occurs. In some cases, the binary tree may be compressed to enhance the search operation. A Patricia tree is one form of compression used to shorten the length of a branch to having relatively few leaf nodes.
As one disadvantage, the longest-matching prefix search techniques described above do not take into account that certain sub-databases or branches may rarely be searched while others are predominantly searched. While a tree proves helpful in locating prefixes within the leaf nodes, a precondition of searching a tree is that before the next node can be fetched, the previous nodes must be retrieved. Empty or sparse routes may, therefore, result in a relatively slow search, and thus, a relatively slow lookup operation.
The speed with which a search or lookup operation is performed could be increased if the prefix entries within each node (or searchable sub-database) were more optimally apportioned. Co-pending application Ser. No. 10/402,887 describes a system and method for configuring sub-databases within the overall forwarding database of a lookup table. In general, the co-pending application describes how the forwarding database may be optimally apportioned by placing bounds on the number of prefixes within each sub-database, and bounds on the number of sub-databases within the lookup table. By controlling the number of sub-databases and the sizes of the sub-databases, lookup operations are more deterministic, and worst-case lookup times can be guaranteed. Moreover, the bounded number of sub-databases can be more optimally apportioned to a physical device, such as a memory, with dedicated portions of the memory appropriately sized to accommodate a corresponding sub-database. This may ultimately lessen the amount of power consumed by the lookup operation, since only one sub-database need be accessed during a particular lookup.
In the co-pending application, the forwarding database is constructed in a static fashion, i.e., once the whole database is known. However, the co-pending application does not describe how to construct or update the forwarding database in an incremental, online fashion when the database is being updated rapidly (which is typically the case in real-life applications). At some points in the Internet, route updates may occur at peak rates of about one-thousand updates per second (with a lower average around a few updates per second). Therefore, a need exists for a system and method for dynamically updating a forwarding database, and more specifically, a system and method capable of obtaining significantly greater update rates than those currently achieved in the worst-case scenario.